package net.carinae.dev.seduku.utils;

import java.io.Serializable;
import java.util.Collection;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.Map.Entry;

import net.carinae.dev.seduku.model.Sudoku4;

import com.google.appengine.repackaged.com.google.common.collect.Maps;
import com.google.common.base.Predicate;
import com.google.common.collect.Collections2;
import com.google.common.collect.HashMultimap;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Multimap;
import com.google.common.collect.Multiset;
import com.google.common.collect.SetMultimap;
import com.google.common.collect.Sets;


/**
 * Sudoku solver and generator.
 * 
 * @see "http://norvig.com/sudoku.html"
 * @author Carlos Vara
 */
public class SudokuGenerator implements Serializable {
    
    public String nextSudoku4() {
        return nextSudoku(SudokuType.FOUR_BY_FOUR);
    }
    
    public String nextSudoku9() { 
        return nextSudoku(SudokuType.NINE_BY_NINE);
    }
    
    private String nextSudoku(SudokuType t) {
        StringBuilder baseBuilder = new StringBuilder();
        for ( int i=0; i<t.allIndexes().length; ++i ) {
            baseBuilder.append(".");
        }
        final InternalSudoku blankBoard = InternalSudoku.fromString(baseBuilder.toString());
        
        Random random = new Random(System.currentTimeMillis());
        
        InternalSudoku sdk = InternalSudoku.copy(blankBoard);
        
        Map<SquareIndex, SudokuDigit> addedDigits = Maps.newHashMap();
        
        while ( true ) {
            
            // First, select a random position in the sudoku
            SquareIndex rndIndex = t.allIndexes()[random.nextInt(t.allIndexes().length)];
            if ( sdk.get(rndIndex).size() < 2 ) {
                continue; // Start again choosing a new index
            }
            
            // And assign it a random digit inside the set of possible ones
            SudokuDigit rndDigit = sdk.get(rndIndex).toArray(new SudokuDigit[0])[random.nextInt(sdk.get(rndIndex).size())];
            if ( null == sdk.assign(rndIndex, rndDigit) ) {
                // Restart the search
                sdk = InternalSudoku.copy(blankBoard);
                addedDigits.clear();
                continue;
            }
            else {
                addedDigits.put(rndIndex, rndDigit);
            }
            
            // Don't search for solutions until at least a few numbers are set
            if ( addedDigits.size() < (t.allIndexes().length*0.25) ) {
                continue;
            }
            
            // Check for the number of solutions
            Set<String> solutions = sdk.findSolutions(2);
            
            if ( solutions.isEmpty() ) {
                // Restart the search
                sdk = InternalSudoku.copy(blankBoard);
                addedDigits.clear();
                continue;
            }
            else if ( solutions.size() == 1 ) {
                // Random sudoku created!
                break;
            }
            
        }
        
        // Create a new sudoku with only the added digits
        StringBuilder sb = new StringBuilder();
        for ( SquareIndex idx : t.allIndexes() ) {
            sb.append(addedDigits.get(idx)!=null?addedDigits.get(idx):".");
        }
        
        return sb.toString();
    }
    
    
    // FIXME: Temporal method to keep compatibility with older generator
    public Sudoku4 generateSudoku() {
        String sudokuInitial = nextSudoku4();
        String solution = InternalSudoku.fromString(sudokuInitial).findSolutions(1).iterator().next();
        return new Sudoku4(sudokuInitial, solution);
    }

    
    /**
     * Internal representation of a sudoku used in the solving and generating algorithms.
     */
    private static class InternalSudoku implements SetMultimap<SquareIndex, SudokuDigit> {
        
        private final SudokuType type;
        
        private final HashMultimap<SquareIndex, SudokuDigit> decorated;
        
        private InternalSudoku(SudokuType st) {
            type = st;
            decorated = HashMultimap.create(type.allIndexes().length, type.allDigits().length);
        }

        /**
         * Creates an InternalSudoku with the board set as indicated in 'rep'.
         * 
         * @param rep
         *            A string representation of a sudoku board.
         * @return The created sudoku.
         */
        public static InternalSudoku fromString(String rep) {
            
            InternalSudoku ret = null;
            
            // Create a blank board with the needed dimensions
            if ( rep.length() == 16 ) {
                ret = new InternalSudoku(SudokuType.FOUR_BY_FOUR);
            }
            else if ( rep.length() == 81 ) {
                ret = new InternalSudoku(SudokuType.NINE_BY_NINE);
            }
            else {
                throw new IllegalArgumentException("Invalid Sudoku string: " + rep + " (invalid dimension)");
            }
            
            ImmutableList<SudokuDigit> immDigits = ImmutableList.of(ret.type.allDigits());
            for ( SquareIndex index : ret.type.allIndexes() ) {
                ret.putAll(index, immDigits);
            }
            
            // Populate the board according to the string
            int pos = 0;
            for (SquareIndex idx : ret.type.allIndexes()) {
                SudokuDigit d;
                try {
                    d = ret.type.digitValueOf("d" + rep.charAt(pos++));
                } catch (IllegalArgumentException e) {
                    continue;
                }
                if ( null == ret.assign(idx, d) ) {
                    throw new IllegalArgumentException("Invalid Sudoku string: " + rep);
                }
            }
            return ret;
        }

        /**
         * Deep copies the original sudoku board.
         * 
         * @param orig
         *            Original sudoku.
         * @return A deep copy of 'orig'.
         */
        public static InternalSudoku copy(InternalSudoku orig) {
            InternalSudoku ret = new InternalSudoku(orig.type);
            for ( SquareIndex square : ret.type.allIndexes() ) {
                ret.putAll(square, orig.get(square));
            }
            return ret;
        }

        /**
         * Assigns a digit into a square. Propagates the constraints.
         * 
         * @param square
         *            The index of the square.
         * @param d
         *            The digit to assign.
         * @return The resulting board if it's a valid move, <code>null</code>
         *         otherwise.
         */
        public InternalSudoku assign(SquareIndex square, SudokuDigit d) {
            
            for ( SudokuDigit d2 : d.complement() ) {
                if ( null == eliminate(square, d2)) {
                    return null;
                }
            }
            
            return this;
        }

        /**
         * Eliminates the digit d from the possible values of a square.
         * Propagates the constraints.
         * 
         * @param square
         *            The index of the square.
         * @param d
         *            The digit to eliminate.
         * @return The resulting board if it's a valid move, <code>null</code>
         *         otherwise.
         */
        public InternalSudoku eliminate(SquareIndex square, final SudokuDigit d) {
            
            // If the digit wasn't there, return as is
            if ( !get(square).remove(d) ) {
                return this;
            }
            
            // If the last value was removed
            if ( get(square).isEmpty() ) {
                return null;
            }
            
            // If it's the only value, eliminte it from the peer squares
            if ( get(square).size() == 1 ) {
                SudokuDigit d2 = get(square).iterator().next();
                for ( SquareIndex peer : square.peers() ) {
                    if ( null == eliminate(peer, d2 )) {
                        return null;
                    }
                }
            }
            
            // For every unit, for all the squares in it check if d is assignable,
            // and if it is only in 1, assign it to it
            for ( SudokuUnits unit : SudokuUnits.values() ) {
                Set<? extends SquareIndex> box = square.unit(unit);
                Collection<? extends SquareIndex> indexesWhereDisAssignable = Collections2.filter(box, new Predicate<SquareIndex>() {
                    @Override
                    public boolean apply(SquareIndex input) {
                        return get(input).contains(d);
                    }
                });
                
                if ( indexesWhereDisAssignable.size() == 0) {
                    return null;
                }
                else if ( indexesWhereDisAssignable.size() == 1) {
                    if ( null == assign(indexesWhereDisAssignable.iterator().next(), d) ) {
                        return null;
                    }
                }
            }
            
            return this;
        }

        /**
         * Indicates whether this Sudoku is solved or not.
         * 
         * @return <code>true</code> if it's solved, <code>false</code>
         *         otherwise.
         */
        public boolean isSolved() {
            boolean solved = true;
            for ( SquareIndex square : keySet() ) {
                solved &= (get(square).size() == 1);
                if ( !solved ) {
                    break;
                }
            }
            return solved;
        }
        
        // Checks if the current sudoku has more than 1 solution
        public Set<String> findSolutions(int max) {
            if (isSolved()) {
                return Sets.newHashSet(this.stringRep());
            }
            
            // Obtain the index with the least assignable values (bigger than 2)
            // Maybe obtaining the sets, filtering the ones with less than 2 size, and ordering by size? 
            int minLen = Integer.MAX_VALUE;
            SquareIndex minSquare = null;
            for (SquareIndex square : type.allIndexes()) {
                if (get(square).size() > 1 && get(square).size() < minLen) {
                    minLen = get(square).size();
                    minSquare = square;
                }
            }
            
            Set<String> ret = Sets.newHashSet();
            for (SudokuDigit d : get(minSquare)) {
                InternalSudoku origCopy = InternalSudoku.copy(this);
                if (null != origCopy.assign(minSquare, d)) {
                    Set<String> vals = origCopy.findSolutions(max);
                    ret.addAll(vals);
                    if ( ret.size() >= max ) {
                        return ret;
                    }
                }
            }

            return ret;
        }
        
        public Set<String> findAllSolutions() {
            return findSolutions(Integer.MAX_VALUE);
        }
        
        
        private String stringRep() {
            StringBuilder sb = new StringBuilder();
            for ( SquareIndex square : type.allIndexes() ) {
                sb.append((get(square).size() == 1)?get(square).iterator().next():".");
            }
            return sb.toString();
        }
        
        
        private String printCell(Set<SudokuDigit> cell, int width) {

            StringBuilder sb = new StringBuilder();
            
            for ( SudokuDigit d : cell ) {
                sb.append(d);
            }

            for (int i = sb.length(); i <= width; ++i) {
                sb.insert(0, " ");
            }

            return sb.toString();
        }


        /**
         * @return The representation of the current Sudoku board, with all the
         *         possible values for each square.
         */
        @Override
        public String toString() {
            
            String ret = "\n";

            int width = 1;
            for (SquareIndex c : decorated.keys()) {
                width = Math.max(width, decorated.get(c).size());
            }

            if (type == SudokuType.FOUR_BY_FOUR) {

                String sep = "-";
                for (int i = 0; i <= width; ++i) {
                    sep += "--";
                }

                for (int y = 0; y < 4; ++y) {
                    if (y == 2) {
                        ret += sep + "+" + sep + "\n";
                    }
                    for (int x = 0; x < 4; ++x) {
                        if (x == 2) {
                            ret += " |";
                        }
                        ret += printCell(this.get(type.allIndexes()[y * 4 + x]), width);
                    }
                    ret += "\n";
                }

            }

            else {

                String sep = "-";
                for (int i = 0; i <= width; ++i) {
                    sep += "---";
                }

                for (int y = 0; y < 9; ++y) {
                    if (y == 3 || y == 6) {
                        ret += sep + "+" + sep + "\n";
                    }
                    for (int x = 0; x < 9; ++x) {
                        if (x == 3 || x == 6 ) {
                            ret += " |";
                        }
                        ret += printCell(this.get(type.allIndexes()[y * 9 + x]), width);
                    }
                    ret += "\n";
                }
                
            }

            return ret;
        }
        

        // Decorated...

        @Override
        public Map<SquareIndex, Collection<SudokuDigit>> asMap() {
            return decorated.asMap();
        }

        @Override
        public Set<Entry<SquareIndex, SudokuDigit>> entries() {
            return decorated.entries();
        }

        @Override
        public Set<SudokuDigit> get(SquareIndex key) {
            return decorated.get(key);
        }

        @Override
        public Set<SudokuDigit> removeAll(Object key) {
            return decorated.removeAll(key);
        }

        @Override
        public Set<SudokuDigit> replaceValues(SquareIndex key, Iterable<? extends SudokuDigit> values) {
            return decorated.replaceValues(key, values);
        }

        @Override
        public void clear() {
            decorated.clear();
        }

        @Override
        public boolean containsEntry(Object key, Object value) {
            return decorated.containsEntry(key, value);
        }

        @Override
        public boolean containsKey(Object key) {
            return decorated.containsKey(key);
        }

        @Override
        public boolean containsValue(Object value) {
            return decorated.containsValue(value);
        }

        @Override
        public boolean isEmpty() {
            return decorated.isEmpty();
        }

        @Override
        public Set<SquareIndex> keySet() {
            return decorated.keySet();
        }

        @Override
        public Multiset<SquareIndex> keys() {
            return decorated.keys();
        }

        @Override
        public boolean put(SquareIndex key, SudokuDigit value) {
            return decorated.put(key, value);
        }

        @Override
        public boolean putAll(Multimap<? extends SquareIndex, ? extends SudokuDigit> multimap) {
            return decorated.putAll(multimap);
        }

        @Override
        public boolean putAll(SquareIndex key, Iterable<? extends SudokuDigit> values) {
            return decorated.putAll(key, values);
        }

        @Override
        public boolean remove(Object key, Object value) {
            return decorated.remove(key, value);
        }

        @Override
        public int size() {
            return decorated.size();
        }

        @Override
        public Collection<SudokuDigit> values() {
            return decorated.values();
        }
        
    }
    
}
